Depth-First Search (DFS) explores as far as possible along each branch before backtracking. It uses a stack (either the program's call stack via recursion, or an explicit one). A key feature of DFS is its ability to record discovery and finish times, which creates a "parenthesis structure" around the exploration of each node and its descendants.
Key Concepts Explained
To understand the timeline, we use two timestamps for each vertex `v`:
- d[v] (Discovery Time): The moment we first visit a vertex. Think of this as "starting a task."
- f[v] (Finish Time): The moment after we have explored all of its descendants. This means "the task and all its sub-tasks are complete."
The animation shows how the interval `[d[v], f[v]]` for a child node is always nested inside its parent's interval. This is the parenthesis structure, and it's useful for detecting cycles and creating topological sorts.
Recursion & Stack
Recursive DFS leverages the call stack to remember the current path; iterative DFS uses an explicit stack. Both realize LIFO order. The recursion depth equals the path length currently being explored.
Each vertex \( v \) gets \( d[v] \) (discovery) and \( f[v] \) (finish), with \( d[v] < f[v] \).